package com.lft.sort10.counting_sort;

import java.util.Arrays;

/**
 * 计数排序（桶排序的升级）
 */
public class CountingSort {
	public static void main(String[] args) {
		int[] a = {2, 6, 9, 3, 5, 1, -9, 7, -3, -1, -6, 8, 0};
		System.out.println(Arrays.toString(countingSort(a)));
	}
	
	public static int[] countingSort(int[] a) {
		int length = a.length;
		int max = a[0];
		int min = a[0];
		// 遍历数组，找到最小值和最大值。
		for (int i = 0; i < length; i++) {
			if (a[i] > max) {
				max = a[i];
			} else if (a[i] < min) {
				min = a[i];
			}
		}
		
		// 通过最大值和最小值确定桶的数量
		int bucketLength = max - min + 1;
		// 创建桶数组。
		int[] buckets = new int[bucketLength];
		
		int tempIndex;
		for (int i = 0; i < length; i++) {
			// a[i] - min 确定桶的索引
			tempIndex = a[i] - min;
			// 然后将桶的值加 1
			buckets[tempIndex]++;
		}
		// 从小到大排序
		for (int i = 1; i < bucketLength; i++) {
			// 后面桶对前面桶的累加
			buckets[i] = buckets[i] + buckets[i - 1];
		}
		
		// // 从大到小排序
		// for (int i = bucketLength - 1; i > 0; i--) {
		// 	buckets[i - 1] = buckets[i] + buckets[i - 1];
		// }
		
		// 以原数组的长度创建一个临时数组。
		int[] temp = new int[length];
		// 把原数组保存到临时数组中。
		System.arraycopy(a, 0, temp, 0, length);
		// 遍历 temp 数组，通过桶找到每个元素的排序位置。
		for (int i = 0; i < length; i++) {
			a[--buckets[temp[i] - min]] = temp[i];
		}
		return a;
	}
}
